7.5 KB · ⇊ 3 parts · ⤓ Micron 7.5 KB · ⤓ HTML 56.6 KB

top

Das Legendre-Symbol ist eine Kurzschreibweise, die in der Zahlentheorie, einem Teilgebiet der Mathematik, verwendet wird. Es ist nach dem französischen Mathematiker Adrien-Marie Legendre benannt.

• Definition und Notation

• Berechnung

• Beispiele

• Rechenregeln

• Spezielle Werte

• Die besondere Stellung der Zahl 3

• Besonderheiten bei Primzahlen

Das Legendre-Symbol gibt an, ob die Zahl a {\displaystyle a} quadratischer Rest modulo p {\displaystyle p} oder quadratischer Nichtrest modulo p {\displaystyle p} ist. Dabei ist a {\displaystyle a} eine ganze Zahl und p {\displaystyle p} eine ungerade Primzahl.

Es gilt

( a p ) = { 1 , wenn a quadratischer Rest modulo p und kein Vielfaches von p ist , − − 1 , wenn a quadratischer Nichtrest modulo p ist , 0 , wenn a ein Vielfaches von p ist . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1,&{\text{wenn }}a{\text{ quadratischer Rest modulo }}p{\text{ und kein Vielfaches von }}p{\text{ ist}},\\-1,&{\text{wenn }}a{\text{ quadratischer Nichtrest modulo }}p{\text{ ist}},\\0,&{\text{wenn }}a{\text{ ein Vielfaches von }}p{\text{ ist}}.\end{cases}}}

Das Legendre-Symbol ist ein Spezialisierung des Jacobi-Symbols, das wiederum eine Spezialisierung des Kronecker-Symbols ist. Alle drei Symbole benutzen daher unmissverständlich dieselbe Schreibweise. Weitere Notationsvarianten für das Legendre-Symbol sind ( a / p ) {\displaystyle (a/p)} und L ( a , p ) {\displaystyle L(a,p)} .

Das eulersche Kriterium gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:

( a p ) ≡ ≡ a p − − 1 2 ( mod p ) {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}} .

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit

( a p ) = sgn ⁡ ⁡ ( π π a , p ) , {\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p}),}

wobei π π a , p {\displaystyle \pi _{a,p}} , die durch

π π a , p ( k ) ≡ ≡ a ⋅ ⋅ k ( mod p ) {\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}

definierte Permutation der Zahlen von k = 0 , … … p − − 1 {\displaystyle k=0,\dotsc p-1} ist, und sgn {\displaystyle \operatorname {sgn} } das Vorzeichen einer Permutation bezeichnet.

2 ist quadratischer Rest modulo 7 – in der Tat ist ja 2 ≡ ≡ 3 2 ( mod 7 ) {\displaystyle 2\equiv 3^{2}{\pmod {7}}} :

( 2 7 ) ≡ ≡ 2 7 − − 1 2 = 2 3 ≡ ≡ 1 mod 7 {\displaystyle \left({\frac {2}{7}}\right)\equiv 2^{\frac {7-1}{2}}=2^{3}\equiv 1\mod 7}

5 ist quadratischer Nichtrest modulo 7:

( 5 7 ) ≡ ≡ 5 7 − − 1 2 = 5 3 ≡ ≡ 6 ≡ ≡ − − 1 mod 7 {\displaystyle \left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7}

14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):

( 14 7 ) ≡ ≡ 14 7 − − 1 2 = 14 3 ≡ ≡ 0 mod 7 {\displaystyle \left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7}

Das quadratische Reziprozitätsgesetz macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.

Außerdem gelten für alle ganze Zahlen a {\displaystyle a} , b {\displaystyle b} und alle Primzahlen p {\displaystyle p} folgende Rechenregeln:

• a ≡ ≡ b ( mod p ) ⇒ ⇒ ( a p ) = ( b p ) {\displaystyle a\equiv b{\pmod {p}}\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}

• ( a p ) ⋅ ⋅ ( b p ) = ( a ⋅ ⋅ b p ) {\displaystyle \left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)}

• ∑ ∑ k = 1 p − − 1 ( k p ) = 0 {\displaystyle \sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)=0} .

Es gilt

( 1 p ) = 1 , {\displaystyle \left({\frac {1}{p}}\right)=1,}

( 2 p ) = ( − − 1 ) p 2 − − 1 8 = { 1 , für p ≡ ≡ 1 oder 7 ( mod 8 ) , − − 1 , für p ≡ ≡ 3 oder 5 ( mod 8 ) , {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\mbox{ oder }}7{\pmod {8}},\\-1,&{\mbox{ für }}p\equiv 3{\mbox{ oder }}5{\pmod {8}},\end{cases}}}

( − − 1 p ) = ( − − 1 ) p − − 1 2 = { 1 , für p ≡ ≡ 1 ( mod 4 ) , − − 1 , für p ≡ ≡ 3 ( mod 4 ) . {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1,&{\mbox{ für }}p\equiv 1{\pmod {4}},\\-1,&{\mbox{ für }}p\equiv 3{\pmod {4}}.\end{cases}}}

Diese speziellen Werte reichen aus, um jedes nicht-verschwindende Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des quadratischen Reziprozitätsgesetzes und modulo-Reduktion zu berechnen. So ist zum Beispiel

( 10 31 ) = ( 2 31 ) ( 5 31 ) = 1 ⋅ ⋅ ( − − 1 ) 5 − − 1 2 31 − − 1 2 ( 31 5 ) = ( 1 5 ) = 1. {\displaystyle \left({\frac {10}{31}}\right)=\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)=1\cdot (-1)^{{\frac {5-1}{2}}{\frac {31-1}{2}}}\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1.}

Die Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0, 1 und −1 zurück. Dies entspricht genau den Werten des Legendre-Symbols. Es gilt also:

( a 3 ) ≡ ≡ a 3 − − 1 2 mod ⁡ ⁡ 3 = a mod ⁡ ⁡ 3 {\displaystyle \left({\frac {a}{3}}\right)\equiv a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}

Andererseits gilt auch:

( 3 p ) = ∏ ∏ l = 1 p − − 1 2 [ 3 − − 4 sin 2 ⁡ ⁡ ( 2 π π l p ) ] {\displaystyle \left({\frac {3}{p}}\right)=\prod _{l=1}^{\frac {p-1}{2}}\left[3-4\,\sin ^{2}{\left({\frac {2\pi l}{p}}\right)}\right]}

Siehe dazu unter Pythagoreische Primzahl.